It is well known that there is a sharp density threshold for a random $r$-SATformula to be satisfiable, and a similar, smaller, threshold for it to besatisfied by the pure literal rule. Also, above the satisfiability threshold,where a random formula is with high probability (whp) unsatisfiable, theunsatisfiability is whp due to a large "minimal unsatisfiable subformula"(MUF). By contrast, we show that for the (rare) unsatisfiable formulae below thepure literal threshold, the unsatisfiability is whp due to a unique MUF withsmallest possible "excess", failing this whp due to a unique MUF with the nextlarger excess, and so forth. In the same regime, we give a precise asymptoticexpansion for the probability that a formula is unsatisfiable, and efficientalgorithms for satisfying a formula or proving its unsatisfiability. It remainsopen what happens between the pure literal threshold and the satisfiabilitythreshold. We prove analogous results for the $k$-core and $k$-colorabilitythresholds for a random graph, or more generally a random $r$-uniformhypergraph.
展开▼
机译：众所周知，对于一个随机的$ r $ -SAT公式，可以满足一个尖锐的密度阈值，而对于纯文字规则，它可以满足一个类似的较小的阈值。同样，在可满足性阈值之上，其中随机公式具有很高的概率（whp）无法满足，由于较大的“最小不可满足子公式”（MUF），所以无法满足性。相比之下，我们表明，对于低于纯字面阈值的（稀有）无法满足的公式，由于唯一的MUF可能具有最小的“超额”，所以无法满足要求，而由于唯一的MUF却要加上下一个更大的超额费用，因此无法满足要求，依此类推。在同一制度下，我们给出了公式不满足的概率的精确渐近展开，以及满足公式或证明其不满足要求的有效算法。纯粹的文字阈值和可满足性阈值之间发生的情况仍然是开放的。我们证明了随机图或更普遍的是随机的$ r $-均匀超图的$ k $核心和$ k $ colorabilitythresholds的相似结果。
展开▼
